package 剑指offer.demo2;

import java.util.ArrayList;
import java.util.Stack;
//https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?

/**
 * 方法一：利用栈完成倒叙输出操作
 * 方法二：递归链表返回过程中添加至动态数组
 */
public class 从尾到头打印链表 {
    public ArrayList<Integer> printListFromTailToHead_1(ListNode listNode) {
        //定义待返回数组
        ArrayList<Integer> arr = new ArrayList<>();
        //合法性判断
        if (listNode == null){
            return arr;
        }
        //倒叙排列，栈结构先进后出
        Stack<Integer> stack = new Stack<>();
        //listNode不是空的化顺序入栈
        while (listNode != null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        //while循环跳出时，所有元素已经存入栈中，出栈让入动态数组就是倒叙
        while (!stack.isEmpty()){
            arr.add(stack.pop());
        }
        return arr;
    }

    public ArrayList<Integer> printListFromTailToHead_2(ListNode listNode) {
        //定义待返回数组
        ArrayList<Integer> arr = new ArrayList<>();
        //合法性判断
        if (listNode == null){
            return arr;
        }
        //调用方法帮助操作（在arr中添加合适的元素）
        fun_2Help(arr , listNode);
        return arr;
    }
    public void fun_2Help(ArrayList<Integer> arr , ListNode listNode){
        //合法性判断,不合法就返回null，也是递归判出条件
        if (listNode == null){
            return ;
        }
        //如果不为空的话继续向下递归到它后面的元素；
        fun_2Help(arr , listNode.next);
        //遇到边界时开始返回把元素添加到动态数组中
        arr.add(listNode.val);
    }


    //题目的listNode类
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

}
